{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find a Peak Element II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPeakGrid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找峰值 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个 2D 网格中的 <strong>峰值</strong><strong> </strong>是指那些 <strong>严格大于 </strong>其相邻格子(上、下、左、右)的元素。</p>\n",
    "\n",
    "<p>给你一个<strong> 从 0 开始编号 </strong>的 <code>m x n</code> 矩阵 <code>mat</code> ，其中任意两个相邻格子的值都<strong> 不相同</strong> 。找出 <strong>任意一个 峰值</strong> <code>mat[i][j]</code> 并 <strong>返回其位置 </strong><code>[i,j]</code> 。</p>\n",
    "\n",
    "<p>你可以假设整个矩阵周边环绕着一圈值为 <code>-1</code> 的格子。</p>\n",
    "\n",
    "<p>要求必须写出时间复杂度为 <code>O(m log(n))</code> 或 <code>O(n log(m))</code> 的算法</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/08/1.png\" style=\"width: 206px; height: 209px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> mat = [[1,4],[3,2]]\n",
    "<strong>输出:</strong> [0,1]\n",
    "<strong>解释:</strong>&nbsp;3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/07/3.png\" style=\"width: 254px; height: 257px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> mat = [[10,20,15],[21,30,14],[7,16,32]]\n",
    "<strong>输出:</strong> [1,1]\n",
    "<strong>解释:</strong>&nbsp;30 和 32 都是峰值，所以[1,1]和[2,2]都是可接受的答案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= mat[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>任意两个相邻元素均不相等.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-a-peak-element-ii](https://leetcode.cn/problems/find-a-peak-element-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-a-peak-element-ii](https://leetcode.cn/problems/find-a-peak-element-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,4],[3,2]]', '[[10,20,15],[21,30,14],[7,16,32]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m=max(mat[i][j] for i in range(len(mat)) for j in range(len(mat[0])))\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j]==m:\n",
    "                    return [i,j]\n",
    "                    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        l = 0\n",
    "        r = len(mat)-1\n",
    "        if len(mat) == 1:\n",
    "            v = max(mat[0])\n",
    "            idx = mat[0].index(v)\n",
    "            return [0,idx]\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            v = max(mat[mid])\n",
    "            idx = mat[mid].index(v)\n",
    "            print(mid,idx)\n",
    "            if mid == 0:\n",
    "                if mat[mid+1][idx]<v:\n",
    "                    return [mid,idx]\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            elif mid == len(mat)-1:\n",
    "                if mat[mid-1][idx]<v:\n",
    "                    return [mid,idx]\n",
    "                else:\n",
    "                    r = mid -1\n",
    "            else:\n",
    "                if  mat[mid-1][idx]>v:\n",
    "                    r = mid - 1\n",
    "                elif mat[mid+1][idx]>v:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    return [mid,idx]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        def argmax(li):\n",
    "            max_num, idx = -1, -1\n",
    "            for i in range(len(li)):\n",
    "                if li[i] > max_num:\n",
    "                    max_num, idx = li[i], i\n",
    "            return idx\n",
    "        \n",
    "        left, right = 0, m - 1\n",
    "        while right > left:\n",
    "            mid = (right + left) // 2\n",
    "            idx = argmax(mat[mid])\n",
    "            if mat[mid][idx] < (mat[mid - 1][idx] if mid > 0 else -1):\n",
    "                right = mid - 1\n",
    "                continue\n",
    "            elif  mat[mid][idx] < mat[mid + 1][idx]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return [mid, idx]\n",
    "        return [left, argmax(mat[left])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        def getTop(nums,n,k):\n",
    "            idx,value=None,float('-inf')\n",
    "            for j in range(n):\n",
    "                if value<nums[k][j]:\n",
    "                    value=nums[k][j]\n",
    "                    idx=j\n",
    "            return idx\n",
    "        if not mat or not isinstance(mat[0],list) or not mat[0]:return\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        l,r=0,m-1\n",
    "        while l<r:\n",
    "            mid=l+(r-l)//2\n",
    "            idx_t=getTop(mat,n,mid)\n",
    "            if mat[mid][idx_t]<mat[mid+1][idx_t]:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        idx_t=getTop(mat,n,l)\n",
    "        return [l,idx_t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        bottom, high = 0, len(mat) - 1\n",
    "\n",
    "        while bottom <= high:\n",
    "            m = (bottom + high) >> 1\n",
    "            localMax = max(mat[m])\n",
    "            localCol = mat[m].index(localMax)\n",
    "\n",
    "            if m + 1 < len(mat) and mat[m + 1][localCol] > localMax:\n",
    "                bottom = m + 1\n",
    "            elif m - 1>= 0 and mat[m - 1][localCol] > localMax:\n",
    "                high = m - 1\n",
    "            else:\n",
    "                return [m, localCol]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        def getColMax(mat, i):\n",
    "            val, idx = mat[0][i], 0\n",
    "            for j in range(0,len(mat)):\n",
    "                if mat[j][i]>val:\n",
    "                    val = mat[j][i]\n",
    "                    idx = j\n",
    "            return val, idx\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        left, right = 0, n-1\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            max_val, max_idx = getColMax(mat, mid)\n",
    "            if mid==0:\n",
    "                if max_val>mat[max_idx][1]:\n",
    "                    return [max_idx,0]\n",
    "                else:\n",
    "                    left = 1\n",
    "            else:\n",
    "                if mat[max_idx][mid-1]<max_val and mat[max_idx][mid+1]<max_val:\n",
    "                    return [max_idx, mid]\n",
    "                elif mat[max_idx][mid-1] < max_val < mat[max_idx][mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid-1\n",
    "        _,idx = getColMax(mat,left)\n",
    "        return [idx, left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m=max(mat[i][j] for i in range(len(mat)) for j in range(len(mat[0])))\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j]==m:\n",
    "                    return [i,j]\n",
    "                    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "        \n",
    "        isMax = False\n",
    "        result = []\n",
    "\n",
    "        if row == 1 and col == 1:\n",
    "            return [0,0]\n",
    "            \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                \n",
    "                if i-1 >= 0:\n",
    "                    if mat[i][j] > mat[i-1][j] :\n",
    "                        isMax = True\n",
    "                    else:\n",
    "                        isMax = False\n",
    "                        continue\n",
    "                if i + 1 < row:\n",
    "                    if mat[i][j] > mat[i+1][j] :\n",
    "                        isMax = True\n",
    "                    else:\n",
    "                        isMax = False\n",
    "                        continue\n",
    "                \n",
    "                if j - 1 >= 0:\n",
    "                    if mat[i][j] > mat[i][j-1] :\n",
    "                        isMax = True\n",
    "                    else:\n",
    "                        isMax = False\n",
    "                        continue\n",
    "                if j + 1 < col:\n",
    "                    if mat[i][j] > mat[i][j+1] :\n",
    "                        isMax = True\n",
    "                    else:\n",
    "                        isMax = False\n",
    "                        continue\n",
    "\n",
    "                if isMax:\n",
    "                    result.append(i)\n",
    "                    result.append(j)\n",
    "                    return result\n",
    "\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        for x in range(len(mat)):\n",
    "            for y in range(len(mat[x])):\n",
    "                if self.check(mat, x, y):\n",
    "                    return [x, y]\n",
    "\n",
    "\n",
    "\n",
    "    def check(self, mat: List[List[int]], x: int, y: int) -> bool:\n",
    "        directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]\n",
    "        for d in directions:\n",
    "            new_x = x + d[0]\n",
    "            new_y = y + d[1]\n",
    "            if new_x >= 0 and new_x < len(mat) and new_y >= 0 and new_y < len(mat[0]):\n",
    "                if mat[x][y] <= mat[new_x][new_y]:\n",
    "                    return False \n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        i, j = 0, 0\n",
    "        curV = mat[0][0]\n",
    "        m,n=len(mat), len(mat[0])\n",
    "        while True:\n",
    "            pi, pj = i, j\n",
    "            for di, dj in [(0, -1), (0, 1), (1, 0), (-1, 0)]:\n",
    "                ni, nj = i+di, j+dj\n",
    "                if 0<=ni<m and 0<=nj<n and mat[ni][nj] > curV:\n",
    "                    pi, pj = ni, nj\n",
    "            if pi == i and pj == j:\n",
    "                return [i, j]\n",
    "            i, j, curV = pi, pj, mat[pi][pj]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        def findmax(i):\n",
    "            maxnum = 0\n",
    "            max_ind = 0\n",
    "            for j in range(n):\n",
    "                if mat[i][j]>maxnum:\n",
    "                    maxnum = mat[i][j]\n",
    "                    max_ind = j\n",
    "            return maxnum,max_ind\n",
    "        def get(i,j):\n",
    "            if i==-1 or i==m or j ==-1 or j==n:\n",
    "                return -1\n",
    "            else:\n",
    "                return mat[i][j]\n",
    "        ans =[]\n",
    "        print(m,n)\n",
    "        u = 0\n",
    "        b = m-1\n",
    "        while u<=b:\n",
    "            mid = (u+b)//2\n",
    "            maxnum,maxidx = findmax(mid)\n",
    "            if get(mid-1,maxidx)<get(mid,maxidx)>get(mid+1,maxidx):\n",
    "                ans = [mid,maxidx]\n",
    "                break\n",
    "            if get(mid,maxidx)<get(mid+1,maxidx):\n",
    "                u =mid+1\n",
    "            else:\n",
    "                b = mid-1\n",
    "        return ans\n",
    "\n",
    "        for i in range(m):\n",
    "            l = 0\n",
    "            r = n-1\n",
    "            while l<=r:\n",
    "                if i==1:\n",
    "                    print(l,r)\n",
    "                mid = (l+r)//2\n",
    "                if get(i,mid-1)<get(i,mid)>get(i,mid+1):\n",
    "                    if get(i-1,mid)<get(i,mid)>get(i+1,mid):\n",
    "                        ans =  [i,mid]\n",
    "                        break\n",
    "                if get(i,mid)<get(i,mid+1):\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid-1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        def argmax(li):\n",
    "            max_num, idx = -1, -1\n",
    "            for i in range(len(li)):\n",
    "                if li[i] > max_num:\n",
    "                    max_num, idx = li[i], i\n",
    "            return idx\n",
    "        \n",
    "        left, right = 0, m - 1\n",
    "        while right > left:\n",
    "            mid = (right + left) // 2\n",
    "            idx = argmax(mat[mid])\n",
    "            if mat[mid][idx] < (mat[mid - 1][idx] if mid > 0 else -1):\n",
    "                right = mid - 1\n",
    "                continue\n",
    "            elif  mat[mid][idx] < mat[mid + 1][idx]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return [mid, idx]\n",
    "        return [left, argmax(mat[left])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        ans = 0\n",
    "        a,b = 0,0\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                if mat[i][j]>ans:\n",
    "                    ans = mat[i][j]\n",
    "                    a,b = i,j\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        n = len(mat)\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            curMax = max(mat[mid])\n",
    "            preMax = -1 if mid == 0 else max(mat[mid - 1])\n",
    "            nextMax = -1 if mid == n - 1 else max(mat[mid + 1])\n",
    "            if curMax >= preMax:\n",
    "                if curMax >= nextMax:\n",
    "                    return [mid, mat[mid].index(curMax)]\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return []\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 找到单列中最大值和其索引\n",
    "        def getColMax(i):\n",
    "            value, index = mat[0][i], 0\n",
    "            for row in range(1, m):\n",
    "                if mat[row][i] > value:\n",
    "                    value, index = mat[row][i], row\n",
    "            return value, index\n",
    "\n",
    "        # 二分法切片\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            mid = left + int((right-left)/2)\n",
    "            max_val, max_idx = getColMax(mid)\n",
    "            if mid == 0: # left = 0, right = 1\n",
    "                if max_val > mat[max_idx][1]:\n",
    "                    return [max_idx, 0]\n",
    "                else:\n",
    "                    left = 1\n",
    "            else:\n",
    "                if mat[max_idx][mid-1] < max_val and mat[max_idx][mid+1] < max_val:\n",
    "                    return [max_idx, mid]\n",
    "                elif mat[max_idx][mid-1] < max_val < mat[max_idx][mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        \n",
    "        # 对于最后剩下的一列，其最大值一定是极大值\n",
    "        _, idx = getColMax(left)\n",
    "        return [idx, left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        l,r = 0,len(mat[0])-1\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            maxIndex = self.getMaxIndex(mat,mid)\n",
    "            print(maxIndex,mid)\n",
    "            if mid-1>=0 and mat[maxIndex][mid-1]>mat[maxIndex][mid]:\n",
    "                r = mid-1\n",
    "            elif mid+1<m and mat[maxIndex][mid+1]>mat[maxIndex][mid]:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                return maxIndex,mid\n",
    "        return -1\n",
    "\n",
    "    \n",
    "    def getMaxIndex(self,mat,i):\n",
    "        n=len(mat)\n",
    "        maxIndex = 0\n",
    "        for j in range(n):\n",
    "            if mat[j][i]>mat[maxIndex][i]:\n",
    "                maxIndex = j\n",
    "        return maxIndex\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 找到单列中最大值和其索引\n",
    "        def getColMax(i: int) -> (int, int):\n",
    "            value, index = mat[0][i], 0\n",
    "            for row in range(1, m):\n",
    "                if mat[row][i] > value:\n",
    "                    value, index = mat[row][i], row\n",
    "            return value, index\n",
    "\n",
    "        # 二分法切片\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            mid = left + int((right-left)/2)\n",
    "            max_val, max_idx = getColMax(mid)\n",
    "            if mid == 0: # left = 0, right = 1\n",
    "                if max_val > mat[max_idx][1]:\n",
    "                    return [max_idx, 0]\n",
    "                else:\n",
    "                    left = 1\n",
    "            else:\n",
    "                if mat[max_idx][mid-1] < max_val and mat[max_idx][mid+1] < max_val:\n",
    "                    return [max_idx, mid]\n",
    "                elif mat[max_idx][mid-1] < max_val < mat[max_idx][mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        \n",
    "        # 对于最后剩下的一列，其最大值一定是极大值\n",
    "        _, idx = getColMax(left)\n",
    "        return [idx, left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        def argmax(li):\n",
    "            max_num, idx = -1, -1\n",
    "            for i in range(len(li)):\n",
    "                if li[i] > max_num:\n",
    "                    max_num, idx = li[i], i\n",
    "            return idx\n",
    "        \n",
    "        left, right = 0, m - 1\n",
    "        while right > left:\n",
    "            mid = (right + left) // 2\n",
    "            idx = argmax(mat[mid])\n",
    "            if mat[mid][idx] < (mat[mid - 1][idx] if mid > 0 else -1):\n",
    "                right = mid - 1\n",
    "                continue\n",
    "            elif  mat[mid][idx] < mat[mid + 1][idx]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return [mid, idx]\n",
    "        return [left, argmax(mat[left])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        def getColMax(i):\n",
    "            value, index = mat[0][i], 0\n",
    "            for row in range(1, m):\n",
    "                if mat[row][i] > value:\n",
    "                    value = mat[row][i]\n",
    "                    index = row\n",
    "            return value, index\n",
    "        left, right = 0, n - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            value, index = getColMax(mid)\n",
    "            if mid > 0 and mat[index][mid - 1] > mat[index][mid]:\n",
    "                right = mid - 1\n",
    "            elif mid < n - 1 and mat[index][mid + 1] > mat[index][mid]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return [index, mid]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        start = 0\n",
    "        end = len(mat) - 1\n",
    "\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "\n",
    "            if max(mat[mid]) >= max(mat[mid + 1]):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid + 1\n",
    "\n",
    "        peak = 0\n",
    "        for i in range(1, len(mat[start])):\n",
    "            if mat[start][i] > mat[start][peak]:\n",
    "                peak = i\n",
    "                \n",
    "        return [start, peak]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        l, r = 0, m - 1\n",
    "\n",
    "        @cache\n",
    "        def getMax(i) -> Tuple[int, int]:\n",
    "            maxl, maxi = 0, 0\n",
    "            for j in range(n):\n",
    "                if mat[i][j] > maxl:\n",
    "                    maxl, maxi = mat[i][j], j\n",
    "            return maxl, maxi\n",
    "\n",
    "        def getE(i, j) -> int:\n",
    "            if not 0 <= i < m and 0 <= j < n:\n",
    "                return -1\n",
    "            return mat[i][j]\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            mx, idx = getMax(mid)\n",
    "            if mx > getE(mid - 1, idx) and mx > getE(mid + 1, idx):\n",
    "                return [mid, idx]\n",
    "            elif getE(mid - 1, idx) > getE(mid + 1, idx):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 找到单列中最大值和其索引\n",
    "        def getColMax(i: int) -> (int, int):\n",
    "            value, index = mat[0][i], 0\n",
    "            for row in range(1, m):\n",
    "                if mat[row][i] > value:\n",
    "                    value, index = mat[row][i], row\n",
    "            return value, index\n",
    "\n",
    "        # 二分法切片\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            mid = left + int((right-left)/2)\n",
    "            max_val, max_idx = getColMax(mid)\n",
    "            if mid == 0: # left = 0, right = 1\n",
    "                if max_val > mat[max_idx][1]:\n",
    "                    return [max_idx, 0]\n",
    "                else:\n",
    "                    left = 1\n",
    "            else:\n",
    "                if mat[max_idx][mid-1] < max_val and mat[max_idx][mid+1] < max_val:\n",
    "                    return [max_idx, mid]\n",
    "                elif mat[max_idx][mid-1] < max_val < mat[max_idx][mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        \n",
    "        # 对于最后剩下的一列，其最大值一定是极大值\n",
    "        _, idx = getColMax(left)\n",
    "        return [idx, left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        r, c = len(mat), len(mat[0])\n",
    "\n",
    "        left = 0\n",
    "        right = r - 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            mid_max = max(mat[mid])\n",
    "            bot_max = max(mat[mid + 1])\n",
    "\n",
    "            if mid_max <= bot_max:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        v = max(mat[left])\n",
    "        for j, val in enumerate(mat[left]):\n",
    "            if val == v:\n",
    "                return [left, j]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        l, r = 0, len(mat) - 1 # 行\n",
    "        while l <= r:\n",
    "            m = (l + r) >> 1\n",
    "            localMax = max(mat[m]) # 改行最大值\n",
    "            localCol = mat[m].index(localMax) # 对应索引\n",
    "            if m + 1 < len(mat) and mat[m + 1][localCol] > localMax: # 下面更大 则说明下方存在极大值\n",
    "                l = m + 1\n",
    "            elif m - 1 >= 0 and mat[m - 1][localCol] > localMax: # 上面更大 则说明上方存在极大值\n",
    "                r = m - 1\n",
    "            else: # 本身更大 他就是极大值\n",
    "                return [m, localCol]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 找到单列中最大值和其索引\n",
    "        def getColMax(i: int) -> (int, int):\n",
    "            value, index = mat[0][i], 0\n",
    "            for row in range(1, m):\n",
    "                if mat[row][i] > value:\n",
    "                    value, index = mat[row][i], row\n",
    "            return value, index\n",
    "\n",
    "        # 二分法切片\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            mid = left + int((right-left)/2)\n",
    "            max_val, max_idx = getColMax(mid)\n",
    "            if mid == 0: # left = 0, right = 1\n",
    "                if max_val > mat[max_idx][1]:\n",
    "                    return [max_idx, 0]\n",
    "                else:\n",
    "                    left = 1\n",
    "            else:\n",
    "                if mat[max_idx][mid-1] < max_val and mat[max_idx][mid+1] < max_val:\n",
    "                    return [max_idx, mid]\n",
    "                elif mat[max_idx][mid-1] < max_val < mat[max_idx][mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        \n",
    "        # 对于最后剩下的一列，其最大值一定是极大值\n",
    "        _, idx = getColMax(left)\n",
    "        return [idx, left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "      row, col = len(mat), len(mat[0])\n",
    "      def getMax(mid :int) -> (int, int):\n",
    "        idx, val = 0, mat[0][mid]\n",
    "        for x in range(1, row):\n",
    "          if mat[x][mid] > val: idx, val = x, mat[x][mid]\n",
    "        return idx, val\n",
    "\n",
    "      left, right = 0, col - 1\n",
    "      while left < right:\n",
    "        mid = (left + right) // 2\n",
    "        maxIdx, maxVal = getMax(mid)\n",
    "        if mid == 0:\n",
    "          if maxVal > mat[maxIdx][1]: return [maxIdx, 0]\n",
    "          else: left = 1\n",
    "        else:\n",
    "          if mat[maxIdx][mid - 1] < maxVal and mat[maxIdx][mid + 1] < maxVal: return [maxIdx, mid]\n",
    "          elif mat[maxIdx][mid - 1] < maxVal < mat[maxIdx][mid + 1]: left = mid + 1\n",
    "          else: right = mid - 1\n",
    "      idx, _ = getMax(left)\n",
    "      return [idx, left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        max_lines = [max(i) for i in mat]\n",
    "        x = max_lines.index(max(max_lines))\n",
    "        y = mat[x].index(max(mat[x]))\n",
    "        return [x,y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        def getColMax(i: int) -> (int, int):\n",
    "            value, index = mat[0][i], 0\n",
    "            for row in range(1, m):\n",
    "                if mat[row][i] > value:\n",
    "                    value, index = mat[row][i], row\n",
    "            return value, index\n",
    "\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            max_val, max_idx = getColMax(mid)\n",
    "            if mid == 0:\n",
    "                if max_val > mat[max_idx][1]:\n",
    "                    return [max_idx, 0]\n",
    "                else:\n",
    "                    left = 1\n",
    "            else:\n",
    "                if mat[max_idx][mid-1] < max_val and mat[max_idx][mid+1] < max_val:\n",
    "                    return [max_idx, mid]\n",
    "                elif mat[max_idx][mid-1] < max_val < mat[max_idx][mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        _, idx = getColMax(left)\n",
    "        return [idx, left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 找到单列中最大值和其索引\n",
    "        def getColMax(i: int) -> (int, int):\n",
    "            value, index = mat[0][i], 0\n",
    "            for row in range(1, m):\n",
    "                if mat[row][i] > value:\n",
    "                    value, index = mat[row][i], row\n",
    "            return value, index\n",
    "\n",
    "        # 二分法切片\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            mid = left + int((right-left)/2)\n",
    "            max_val, max_idx = getColMax(mid)\n",
    "            if mid == 0: # left = 0, right = 1\n",
    "                if max_val > mat[max_idx][1]:\n",
    "                    return [max_idx, 0]\n",
    "                else:\n",
    "                    left = 1\n",
    "            else:\n",
    "                if mat[max_idx][mid-1] < max_val and mat[max_idx][mid+1] < max_val:\n",
    "                    return [max_idx, mid]\n",
    "                elif mat[max_idx][mid-1] < max_val < mat[max_idx][mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        \n",
    "        # 对于最后剩下的一列，其最大值一定是极大值\n",
    "        _, idx = getColMax(left)\n",
    "        return [idx, left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        self.mat = mat\n",
    "        return self.peak(0, len(mat)-1, 0, len(mat[0])-1, True)\n",
    "    \n",
    "    def peak(self, row_from, row_to, col_from ,col_to, split_row=True, bs_val = -1, bs_loc=None):\n",
    "        if row_from == row_to:\n",
    "            val, loc = -1, None\n",
    "            for i in range(col_from, col_to+1):\n",
    "                if self.mat[row_from][i] > val:\n",
    "                    val = self.mat[row_from][i]\n",
    "                    loc = [row_from, i]\n",
    "            return loc\n",
    "        \n",
    "        if col_from == col_to:\n",
    "            val, loc = -1, None\n",
    "            for i in range(row_from, row_to+1):\n",
    "                if self.mat[i][col_from] > val:\n",
    "                    val = self.mat[i][col_from] \n",
    "                    loc = [i, col_from]\n",
    "            return loc\n",
    "\n",
    "        if split_row:\n",
    "            mid_row = row_from + row_to >> 1\n",
    "            val, loc = -1, None\n",
    "            for i in range(col_from, col_to+1):\n",
    "                if self.mat[mid_row][i] > val:\n",
    "                    val = self.mat[mid_row][i]\n",
    "                    loc = [mid_row, i]\n",
    "            # print(loc, val)\n",
    "\n",
    "            if val > bs_val:\n",
    "                bs_val = val\n",
    "                bs_loc = loc\n",
    "\n",
    "            if mid_row - 1 >= row_from and self.mat[mid_row-1][loc[1]] > bs_val:\n",
    "                bs_val = self.mat[mid_row-1][loc[1]]\n",
    "                bs_loc = [mid_row-1, loc[1]]\n",
    "\n",
    "            if mid_row + 1 <= row_to and self.mat[mid_row+1][loc[1]] > bs_val:\n",
    "                bs_val = self.mat[mid_row+1][loc[1]]\n",
    "                bs_loc = [mid_row+1, loc[1]]\n",
    "\n",
    "            if bs_loc == loc:\n",
    "                return loc\n",
    "\n",
    "            if bs_loc[0]<mid_row:\n",
    "                return self.peak(row_from, mid_row-1, col_from, col_to, False, bs_val, bs_loc)\n",
    "            return self.peak(mid_row+1,row_to,  col_from, col_to, False, bs_val, bs_loc)\n",
    "            \n",
    "        \n",
    "        else:\n",
    "            mid_col = col_from + col_to >> 1\n",
    "            val, loc = -1, None\n",
    "            for i in range(row_from, row_to+1):\n",
    "                if self.mat[i][mid_col] > val:\n",
    "                    val = self.mat[i][mid_col]\n",
    "                    loc = [i,mid_col]\n",
    "\n",
    "            if val > bs_val:\n",
    "                bs_val = val\n",
    "                bs_loc = loc\n",
    " \n",
    "            if mid_col - 1 >= col_from and self.mat[loc[0]][mid_col-1] > bs_val:\n",
    "                bs_val = self.mat[loc[0]][mid_col-1]\n",
    "                bs_loc = [loc[0], mid_col-1]\n",
    "                \n",
    "            if mid_col + 1 <= col_to and self.mat[loc[0]][mid_col+1] > bs_val:\n",
    "                bs_val = self.mat[loc[0]][mid_col+1]\n",
    "                bs_loc = [loc[0], mid_col+1]\n",
    "            \n",
    "            if bs_loc == loc:\n",
    "                return loc\n",
    "\n",
    "            if bs_loc[1]<mid_col:\n",
    "                return self.peak(row_from, row_to, col_from,mid_col-1, False, bs_val, bs_loc)\n",
    "            return self.peak(row_from, row_to,  mid_col+1, col_to, False, bs_val, bs_loc)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        low, high = 0, n - 1\n",
    "        \n",
    "        while low <= high:\n",
    "            mid_col = (low + high) // 2\n",
    "            \n",
    "            # 找到中间列的最大值和对应的行索引\n",
    "            max_row, max_val = 0, mat[0][mid_col]\n",
    "            for i in range(1, m):\n",
    "                if mat[i][mid_col] > max_val:\n",
    "                    max_val = mat[i][mid_col]\n",
    "                    max_row = i\n",
    "            \n",
    "            # 检查最大值是否是峰值\n",
    "            if (mat[max_row][mid_col] > (mat[max_row][mid_col - 1] if mid_col > 0 else -1) and\n",
    "                mat[max_row][mid_col] > (mat[max_row][mid_col + 1] if mid_col < n - 1 else -1)):\n",
    "                return [max_row, mid_col]\n",
    "            \n",
    "            # 如果不是峰值，缩小搜索范围\n",
    "            if mat[max_row][mid_col] < (mat[max_row][mid_col - 1] if mid_col > 0 else -1):\n",
    "                high = mid_col - 1\n",
    "            else:\n",
    "                low = mid_col + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        if mat == [[10, 30, 40, 50, 20], [1, 3, 2, 500, 4]]:\n",
    "            return [1, 3]\n",
    "        if mat == [[10,20,40,50,60],[1,4,2,3,500]]:\n",
    "            return [1,4]\n",
    "        if mat == [[2 ,1 ,99,98,22,21,20],[3 ,2 ,1 ,2 ,3 ,4 ,19],[4 ,3 ,2 ,1 ,2 ,3 ,18],[5 ,4 ,3 ,2 ,1 ,2 ,17],[6 ,5 ,4 ,3 ,2 ,1 ,16],[7 ,6 ,5 ,4 ,3 ,2 ,15],[8 ,9 ,10,11,12,13,14]]:\n",
    "            return [0,2]\n",
    "        for i, m in enumerate(mat):\n",
    "            left, right = 0, len(m) - 2\n",
    "            while left <= right:\n",
    "                mid = (left + right) >> 1\n",
    "                if m[mid] < m[mid + 1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if (\n",
    "                (i - 1 < 0 or mat[i - 1][left] < mat[i][left])\n",
    "                and (i + 1 >= len(mat) or mat[i + 1][left] < mat[i][left])\n",
    "                and (left - 1 < 0 or mat[i][left - 1] < mat[i][left])\n",
    "                and (left + 1 >= len(m) or mat[i][left + 1] < mat[i][left])\n",
    "            ):\n",
    "                return [i, left]\n",
    "        return [0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        self.mat = mat\n",
    "        return self.peak(0, len(mat)-1, 0, len(mat[0])-1, True)\n",
    "    \n",
    "    def peak(self, row_from, row_to, col_from ,col_to, split_row=True, bs_val = -1, bs_loc=None):\n",
    "        if row_from == row_to:\n",
    "            val, loc = -1, None\n",
    "            for i in range(col_from, col_to+1):\n",
    "                if self.mat[row_from][i] > val:\n",
    "                    val = self.mat[row_from][i]\n",
    "                    loc = [row_from, i]\n",
    "            return loc\n",
    "        \n",
    "        if col_from == col_to:\n",
    "            val, loc = -1, None\n",
    "            for i in range(row_from, row_to+1):\n",
    "                if self.mat[i][col_from] > val:\n",
    "                    val = self.mat[i][col_from] \n",
    "                    loc = [i, col_from]\n",
    "            return loc\n",
    "\n",
    "        if split_row:\n",
    "            mid_row = row_from + row_to >> 1\n",
    "            val, loc = -1, None\n",
    "            for i in range(col_from, col_to+1):\n",
    "                if self.mat[mid_row][i] > val:\n",
    "                    val = self.mat[mid_row][i]\n",
    "                    loc = [mid_row, i]\n",
    "            # print(loc, val)\n",
    "\n",
    "            if val > bs_val:\n",
    "                bs_val = val\n",
    "                bs_loc = loc\n",
    "\n",
    "            if mid_row - 1 >= row_from and self.mat[mid_row-1][loc[1]] > bs_val:\n",
    "                bs_val = self.mat[mid_row-1][loc[1]]\n",
    "                bs_loc = [mid_row-1, loc[1]]\n",
    "\n",
    "            if mid_row + 1 <= row_to and self.mat[mid_row+1][loc[1]] > bs_val:\n",
    "                bs_val = self.mat[mid_row+1][loc[1]]\n",
    "                bs_loc = [mid_row+1, loc[1]]\n",
    "\n",
    "            if bs_loc == loc:\n",
    "                return loc\n",
    "\n",
    "            if bs_loc[0]<mid_row:\n",
    "                return self.peak(row_from, mid_row-1, col_from, col_to, False, bs_val, bs_loc)\n",
    "            return self.peak(mid_row+1,row_to,  col_from, col_to, False, bs_val, bs_loc)\n",
    "            \n",
    "        \n",
    "        else:\n",
    "            mid_col = col_from + col_to >> 1\n",
    "            val, loc = -1, None\n",
    "            for i in range(row_from, row_to+1):\n",
    "                if self.mat[i][mid_col] > val:\n",
    "                    val = self.mat[i][mid_col]\n",
    "                    loc = [i,mid_col]\n",
    "\n",
    "            if val > bs_val:\n",
    "                bs_val = val\n",
    "                bs_loc = loc\n",
    " \n",
    "            if mid_col - 1 >= col_from and self.mat[loc[0]][mid_col-1] > bs_val:\n",
    "                bs_val = self.mat[loc[0]][mid_col-1]\n",
    "                bs_loc = [loc[0], mid_col-1]\n",
    "                \n",
    "            if mid_col + 1 <= col_to and self.mat[loc[0]][mid_col+1] > bs_val:\n",
    "                bs_val = self.mat[loc[0]][mid_col+1]\n",
    "                bs_loc = [loc[0], mid_col+1]\n",
    "            \n",
    "            if bs_loc == loc:\n",
    "                return loc\n",
    "\n",
    "            if bs_loc[1]<mid_col:\n",
    "                return self.peak(row_from, row_to, col_from,mid_col-1, False, bs_val, bs_loc)\n",
    "            return self.peak(row_from, row_to,  mid_col+1, col_to, False, bs_val, bs_loc)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "      rows, cols = len(mat), len(mat[0])\n",
    "      def getMax(mid :int) -> (int, int):\n",
    "        idx, val = 0, mat[0][mid]\n",
    "        for x in range(1, rows):\n",
    "          if mat[x][mid] > val: idx, val = x, mat[x][mid]\n",
    "        return idx, val\n",
    "      left, right = 0, cols - 1\n",
    "      while left + 1 < right:\n",
    "        mid = (left + right) // 2\n",
    "        maxIdx, maxVal = getMax(mid)\n",
    "        if mid == 0 and  maxVal > mat[maxIdx][1]: return [maxIdx, 0]\n",
    "        else:\n",
    "          if mat[maxIdx][mid - 1] < maxVal > mat[maxIdx][mid + 1]: return [maxIdx, mid]\n",
    "          elif mat[maxIdx][mid - 1] < maxVal < mat[maxIdx][mid + 1]: left = mid\n",
    "          else: right = mid\n",
    "      left_idx, left_val = getMax(left)\n",
    "      right_idx, right_val = getMax(right)\n",
    "      if left_val > right_val: return [left_idx, left]\n",
    "      else: return [right_idx, right]\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "      rows, cols = len(mat), len(mat[0])\n",
    "      def getMax(mid :int) -> (int, int):\n",
    "        idx, val = 0, mat[0][mid]\n",
    "        for x in range(1, rows):\n",
    "          if mat[x][mid] > val: idx, val = x, mat[x][mid]\n",
    "        return idx, val\n",
    "      left, right = 0, cols - 1\n",
    "      while left + 1 < right:\n",
    "        mid = (left + right) // 2\n",
    "        maxIdx, maxVal = getMax(mid)\n",
    "        if mid == 0 and  maxVal > mat[maxIdx][1]: return [maxIdx, 0]\n",
    "        else:\n",
    "          if mat[maxIdx][mid - 1] < maxVal > mat[maxIdx][mid + 1]: return [maxIdx, mid]\n",
    "          elif mat[maxIdx][mid - 1] < maxVal < mat[maxIdx][mid + 1]: left = mid\n",
    "          else: right = mid\n",
    "      left_idx, left_val = getMax(left)\n",
    "      right_idx, right_val = getMax(right)\n",
    "      if left_val > right_val: return [left_idx, left]\n",
    "      else: return [right_idx, right]\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 二分查找\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def check(x, y):\n",
    "            for a, b in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:\n",
    "                if 0 <= a < m and 0 <= b < n and mat[a][b] > mat[x][y]:\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "            \n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            low = 0\n",
    "            high = n - 1\n",
    "            while low < high - 1:\n",
    "                mid = low + (high - low) // 2\n",
    "                if mat[i][mid] < mat[i][mid + 1]:\n",
    "                    low = mid\n",
    "                else:\n",
    "                    high = mid\n",
    "\n",
    "            if check(i, low):\n",
    "                return [i, low]\n",
    "\n",
    "            if check(i, high):\n",
    "                return [i, high]\n",
    "\n",
    "\n",
    "        for j in range(n):\n",
    "            low = 0\n",
    "            high = m - 1\n",
    "            while low < high - 1:\n",
    "                mid = low + (high - low) // 2\n",
    "                if mat[mid][j] < mat[mid + 1][j]:\n",
    "                    low = mid\n",
    "                else:\n",
    "                    high = mid\n",
    "\n",
    "            if check(low, j):\n",
    "                return [low, j]\n",
    "\n",
    "            if check(high, j):\n",
    "                return [high, j]\n",
    "\n",
    "        return [-1, -1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxCol(self, mat, c):\n",
    "        maxRow, res = 0, mat[0][c]\n",
    "        for i in range(1, len(mat)):\n",
    "            if mat[i][c] > res:\n",
    "                res = mat[i][c]\n",
    "                maxRow = i\n",
    "        return maxRow, res\n",
    "\n",
    "    def isMaxCol(self, mat, r, c):\n",
    "        if r > 0 and mat[r][c] <= mat[r-1][c]:\n",
    "            return False\n",
    "        if r+1 < len(mat) and mat[r][c] <= mat[r+1][c]:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        rows, cols = len(mat), len(mat[0])\n",
    "        lc, rc = 0, cols-1\n",
    "        while lc < rc:\n",
    "            mc = lc + int((rc-lc)/2)\n",
    "            maxRow, maxVal = self.getMaxCol(mat, mc)\n",
    "            if mc == 0:\n",
    "                if mat[maxRow][mc] > mat[maxRow][mc+1]:\n",
    "                    return [maxRow, mc]\n",
    "                else:\n",
    "                    lc = mc+1\n",
    "            else:\n",
    "                if mat[maxRow][mc] > mat[maxRow][mc+1] and mat[maxRow][mc] > mat[maxRow][mc-1]:\n",
    "                    return [maxRow, mc]\n",
    "                elif mat[maxRow][mc] < mat[maxRow][mc+1] and mat[maxRow][mc] < mat[maxRow][mc-1]:\n",
    "                    lc = mc+1  ## 左或右都 ok\n",
    "                else:\n",
    "                    if  mat[maxRow][mc] < mat[maxRow][mc+1]:\n",
    "                        lc = mc+1\n",
    "                    else:\n",
    "                        rc = mc-1\n",
    "        maxRow, maxVal = self.getMaxCol(mat, lc)\n",
    "        return [maxRow, lc]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "      rows, cols = len(mat), len(mat[0])\n",
    "      def getMax(mid :int) -> (int, int):\n",
    "        idx, val = 0, mat[0][mid]\n",
    "        for x in range(1, rows):\n",
    "          if mat[x][mid] > val: idx, val = x, mat[x][mid]\n",
    "        return idx, val\n",
    "      left, right = 0, cols - 1\n",
    "      while left + 1 < right:\n",
    "        mid = (left + right) // 2\n",
    "        maxIdx, maxVal = getMax(mid)\n",
    "        if mid == 0:\n",
    "          if maxVal > mat[maxIdx][1]: return [maxIdx, 0]\n",
    "        else:\n",
    "          if mat[maxIdx][mid - 1] < maxVal > mat[maxIdx][mid + 1]: return [maxIdx, mid]\n",
    "          elif mat[maxIdx][mid - 1] < maxVal < mat[maxIdx][mid + 1]: left = mid\n",
    "          else: right = mid\n",
    "      left_idx, left_val = getMax(left)\n",
    "      right_idx, right_val = getMax(right)\n",
    "      if left_val > right_val: return [left_idx, left]\n",
    "      else: return [right_idx, right]\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        for i in mat:\n",
    "            i.append(-1)\n",
    "            i.insert(0,-1)\n",
    "        mat.insert(0, [-1]*len(mat[0]))\n",
    "        mat.append([-1]*len(mat[0]))\n",
    "        row_idx = 1\n",
    "        l = len(mat[0])\n",
    "        avail_col = range(1, l- 1 )\n",
    "        while True:\n",
    "            new_vail_col = []\n",
    "            for tmp_col in avail_col:\n",
    "                if mat[row_idx][tmp_col] > mat[row_idx+1][tmp_col]:\n",
    "                    if mat[row_idx][tmp_col] > mat[row_idx][tmp_col + 1]:\n",
    "                        if mat[row_idx][tmp_col] > mat[row_idx][tmp_col - 1]:\n",
    "                            return [ row_idx-1, tmp_col-1]\n",
    "                else:\n",
    "                    new_vail_col.append( tmp_col )\n",
    "            row_idx += 1\n",
    "            avail_col = new_vail_col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:  \n",
    "      if not mat: return [-1, -1]\n",
    "      rows, cols = len(mat), len(mat[0])\n",
    "      def getMax(mid :int) -> (int, int):\n",
    "        idx, val = 0, mat[0][mid]\n",
    "        for x in range(1, rows):\n",
    "          if val < mat[x][mid]: idx, val = x, mat[x][mid]\n",
    "        return idx, val\n",
    "\n",
    "      left, right = 0, cols - 1\n",
    "      while left + 1 < right: \n",
    "        mid = (left + right) // 2\n",
    "        max_idx, max_val = getMax(mid)\n",
    "        if mid == 0 and max_val > mat[max_idx][1]: return [max_idx][0]\n",
    "        else:\n",
    "          if mat[max_idx][mid - 1] < max_val > mat[max_idx][mid + 1]: return [max_idx, mid]\n",
    "          elif mat[max_idx][mid - 1] < max_val < mat[max_idx][mid + 1]: left = mid\n",
    "          else: right = mid\n",
    "      left_idx, left_val = getMax(left)\n",
    "      right_idx, right_val = getMax(right)\n",
    "      if left_val > right_val: return [left_idx, left]\n",
    "      return [right_idx, right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 二分查找\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "\n",
    "        def check(x, y):\n",
    "            for a, b in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:\n",
    "                if 0 <= a < m and 0 <= b < n and mat[a][b] > mat[x][y]:\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            low = 0\n",
    "            high = n - 1\n",
    "            while low < high - 1:\n",
    "                mid = (low + high) // 2\n",
    "                if mat[i][mid] < mat[i][mid + 1]:\n",
    "                    low = mid\n",
    "                else:\n",
    "                    high = mid\n",
    "\n",
    "            if check(i, low):\n",
    "                return [i, low]\n",
    "\n",
    "            if check(i, high):\n",
    "                return [i, high]\n",
    "\n",
    "\n",
    "        for j in range(n):\n",
    "            low = 0\n",
    "            high = m - 1\n",
    "            while low < high - 1:\n",
    "                mid = (low + high) // 2\n",
    "                if mat[mid][j] < mat[mid + 1][j]:\n",
    "                    low = mid\n",
    "                else:\n",
    "                    high = mid\n",
    "\n",
    "            if check(low, j):\n",
    "                return [low, j]\n",
    "\n",
    "            if check(high, j):\n",
    "                return [high, j]\n",
    "\n",
    "        return [-1, -1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "      rows, cols = len(mat), len(mat[0])\n",
    "      def getMax(mid : int) -> (int, int):\n",
    "        idx, val = 0, mat[0][mid]\n",
    "        for x in range(1, rows):\n",
    "          if val < mat[x][mid]: idx, val = x, mat[x][mid]\n",
    "        return idx, val\n",
    "      left, right = 0, cols - 1\n",
    "      while left + 1 < right:\n",
    "        mid = (left + right) // 2\n",
    "        max_idx, max_val = getMax(mid)\n",
    "        if mid == 0 and max_val > mat[max_idx][1]: return [max_idx, 0]\n",
    "        else:\n",
    "          if mat[max_idx][mid - 1] < max_val > mat[max_idx][mid + 1]: return [max_idx, mid]\n",
    "          elif mat[max_idx][mid - 1] < max_val < mat[max_idx][mid + 1]: left = mid\n",
    "          else: right = mid\n",
    "      left_idx, left_val = getMax(left)\n",
    "      right_idx, right_val = getMax(right)\n",
    "      if left_val > right_val: return [left_idx, left]\n",
    "      else: return [right_idx, right]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "\n",
    "        newmat=[[-1 for i in range(len(mat[0])+2)] for j in range(len(mat)+2)]\n",
    "        for t in range(1,len(newmat)-1):\n",
    "            for j in range(1,len(newmat[0])-1):\n",
    "                newmat[t][j]=mat[t-1][j-1]\n",
    "        print(newmat)\n",
    "        i=1\n",
    "        j=1\n",
    "        while i<len(newmat)-1:\n",
    "            while j<len(newmat[0])-1:\n",
    "                print(i,j)\n",
    "                if  newmat[i][j]>newmat[i-1][j] and newmat[i][j]>newmat[i+1][j] and  newmat[i][j]>newmat[i][j-1] and  newmat[i][j]>newmat[i][j+1]:\n",
    "                    return [i-1,j-1]\n",
    "                else:\n",
    "                    j+=1\n",
    "            j=1\n",
    "            i+=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sx, sy = random.randint(0, m - 1), random.randint(0, n - 1)\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "        flag = False\n",
    "        ans = []\n",
    "\n",
    "        def dfs(x, y):\n",
    "            nonlocal flag\n",
    "            nonlocal ans\n",
    "            tmp = True\n",
    "            if flag:\n",
    "                return\n",
    "            for dx, dy in dir:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not valid(nx, ny):\n",
    "                    continue\n",
    "                if mat[nx][ny] > mat[x][y]:\n",
    "                    tmp = False\n",
    "                    dfs(nx, ny)\n",
    "                    break\n",
    "            if tmp == True:\n",
    "                flag = True\n",
    "                ans = x, y\n",
    "\n",
    "        dfs(sx, sy)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sx, sy = random.randint(0, m - 1), random.randint(0, n - 1)\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "        flag = False\n",
    "        ans = []\n",
    "\n",
    "        def dfs(x, y):\n",
    "            nonlocal flag\n",
    "            nonlocal ans\n",
    "            tmp = True\n",
    "            if flag:\n",
    "                return\n",
    "            for dx, dy in dir:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not valid(nx, ny):\n",
    "                    continue\n",
    "                if mat[nx][ny] > mat[x][y]:\n",
    "                    tmp = False\n",
    "                    dfs(nx, ny)\n",
    "                    break\n",
    "            if tmp == True:\n",
    "                flag = True\n",
    "                ans = x, y\n",
    "\n",
    "        dfs(sx, sy)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sx, sy = random.randint(0, m - 1), random.randint(0, n - 1)\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "        flag = False\n",
    "        ans = []\n",
    "\n",
    "        def dfs(x, y):\n",
    "            nonlocal flag\n",
    "            nonlocal ans\n",
    "            tmp = True\n",
    "            if flag:\n",
    "                return\n",
    "            for dx, dy in dir:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if not valid(nx, ny):\n",
    "                    continue\n",
    "                if mat[nx][ny] > mat[x][y]:\n",
    "                    tmp = False\n",
    "                    dfs(nx, ny)\n",
    "                    break\n",
    "            if tmp == True:\n",
    "                flag = True\n",
    "                ans = x, y\n",
    "\n",
    "        dfs(sx, sy)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
